#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode *next;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class lowestAncestor {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (root == nullptr)
            // 空指针直接返回
            return nullptr;
        if (root == p || root == q)
            // 当前访问root是p或者q，则直接返回root
            return root;
        
        // 递归获取root->left和root->right中p和q的最近公共祖先
        TreeNode *left = lowestCommonAncestor(root->left, p, q);
        TreeNode *right = lowestCommonAncestor(root->right, p, q);
        if (left == nullptr && right == nullptr)
            // left和right都为空，说明p和q无公共祖先
            return nullptr;
        if (left != nullptr && right != nullptr)
            // left和right都不为空，说明p和q公共祖先为root
            return root;
        // left或right为空，说明不为空的是p和q的公共祖先
        return left == nullptr ? right : left;
    }
};